In programming, a “thread” can be thought of as a minimum “unit of execution” or a basic unit of CPU utilization. The thread model is a flexible process organization mechanism that allows individual processes to access common resources, thereby increasing program efficiency. Namely, a process that has multiple threads of control can perform more than one task at a time. For example, on a single processor machine, this means processing threads on a time-interleaved basis, thereby requiring scheduling. Although the thread model provides the benefit of concurrency of processes, it is up to the operating system or kernel to perform thread scheduling to properly exploit this concurrency.
For example, most operating systems schedule threads to handle interrupts by simply placing them into a queue. The threads are then processed in the order that the threads were scheduled (e.g., threads scheduled to be performed in the order the corresponding interrupts were received). However, this approach does not distinguish the priority of the underlining processes that are performed by the threads in the queue. For example, interrupt threads will be mixed with non-interrupt threads for scheduling.
To address the issue of priority, some advanced operating systems have two queues, where one queue is dedicated to high priority processes and one queue is dedicated to address low priority processes. In this approach, an interrupt thread can be scheduled by being placed in either queue. The threads in the queues are then processed in the order that they were placed in each queue. Although this approach allows the operating system some flexibility in prioritizing the execution of threads, it is still insufficient to allow the operating system to finely schedule threads to account for other parameters, e.g., latency requirement of a particular process.
For example, some real-time devices have “isochronous” requirements, where isochronous denotes “at the same rate”, e.g., where a data flow is tied to time. To illustrate, from the perspective of a hardware device that is receiving a stream of real-time data (e.g., audio and video), the hardware device must handle a plurality of interrupts efficiently to address various functions such as buffer management (e.g., detecting fullness of a first buffer, setting up a second buffer, switching from the full buffer to an available empty buffer and the like). In other words, there is a fixed time limit when the first buffer is full and the second buffer must be ready to receive the continuous data stream. Since the data stream is directed toward the hardware device in real time, the hardware device must handle the interrupts skillfully to avoid a “pop” in the audio or a noticeable “glitch” in presenting the video if data packets are lost due to the inability of the hardware device to keep up with the continuous data stream.
Unlike a “closed” system where timing constraints are known a priori, the above timing criticality is further amplified in an open system, where additional hardware devices or boards can be optionally added. The operating system (OS) for the open system must skillfully balance the timing constraints of these different hardware devices so that they can all operate properly without accidental loss of data due to improper handling of interrupt events.
Additionally, operating systems that are designed to distinguish high priority events from low priority events are often defeated by selfish motives of hardware manufacturers. Specifically, device drivers for hardware devices that are deployed in an open system are often written such that their interrupts will always be considered by the operating system to be high priority. Since each hardware device is competing for service by the operating system, there is little incentive to design a device driver that will cause its interrupts to be considered by the operating system as being low priority.
Additionally, even if interrupts from competing hardware devices are truly equal in terms of being in the same priority class, the operating system will not have any additional information to discriminate between numerous interrupt events. In such instances, the interrupts will likely be processed in the order that they are received in the queue, thereby limiting the ability of the operating system to flexibly rearrange the scheduled threads.
Therefore, a need exists for a novel method and apparatus that provides a thread scheduling approach that allows the operating system to finely schedule threads to account for thread parameters or attributes such as latency of a process and the like.